題目

如果進制為k的n的所有位數均為1，則稱k為n的Good base。

給定一個以string儲存的整數n，求 Smallest Good Base。

• Notes
  • k>=2
  • n範圍: [3, 10^18]
  • 儲存n的string不具前導0
    • e.g. n=1234567，不會出現 0001234567。

解析

• 不管如何，先將string轉回數字，才好使用。
  • 因為範圍只到10^18，使用unsigned long long 就能儲存了。

  uint64_t ull_n = stoull(n);
  

• 接著考慮一下k的範圍，這樣才不用多算沒用的東西。
  • 題目說k>=2
  • 那以k=2至少需要幾位元才能表達n?
    • 2^b >= n
    • 反過來說， 2 = ceil( n^(1/b) )，如果用比b大的值，算出來的base就會小於2。
    • 則能得max如下，記得這max是至少需要的位元數，不是base，但能透過來算出base.
    • min則會是2，這不用多說了吧

    uint64_t min = 2
    uint64_t max = log2(ull_n) + 1 
    

• 有了[min,max]，我們能用for loop，算出每個可能的k，並去看是否符合Good base規定。
  • 這裡i從max開始，即是從最小base開始，有找到就能結束了
  • 先算k，k<2的跳過。
  • 接著算sum為以k為基底的111...1，下面j=1~i+1，因為i是所需位元數，如果在這之間都是每位都是1還不能等於n，那就不會是了。

 for(uint64_t i = max; i >= min; i--){
    uint64_t k = pow(ull_n, 1.0/i); //
    if(k < 2){
        continue;
    }

    uint64_t sum = 0; 
    uint64_t prod = 1;

    for(uint64_t j = 1; j <= i + 1; j++){
        sum += prod;
        prod *= k;
    }

    if(sum == ull_n){
        return to_string(k);
    }
}

完整Code

class Solution {
public:
    string smallestGoodBase(string n) {
        
        uint64_t ull_n = stoull(n);
        uint64_t min = 2;
        uint64_t max = log2(ull_n) + 1;
        
        for(uint64_t i = max; i >= min; i--){
            uint64_t k = pow(ull_n, 1.0/i); //
            if(k < 2){
                continue;
            }
            
            uint64_t sum = 0; 
            uint64_t prod = 1;
            
            for(uint64_t j = 1; j <= i + 1; j++){
                sum += prod;
                prod *= k;
            }
            
            if(sum == ull_n){
                return to_string(k);
            }
        }
        
        return to_string(ull_n - 1);
    }
};